package algorithms.weekly.class01;

import common.util.MyUtil;

/**
 * 我们正在玩一个猜数游戏，游戏规则如下：
 * 我从1到 n 之间选择一个数字。
 * 你来猜我选了哪个数字。
 * 如果你猜到正确的数字，就会 赢得游戏 。
 * 如果你猜错了，那么我会告诉你，我选的数字比你的 更大或者更小 ，并且你需要继续猜数。
 * 每当你猜了数字 x 并且猜错了的时候，你需要支付金额为 x 的现金。
 * 如果你花光了钱，就会 输掉游戏 。
 * 给你一个特定的数字 n ，返回能够 确保你获胜 的最小现金数，不管我选择那个数字 。
 *
 * @author guichang
 * @date 2021/12/26
 */


// TODO 改动态规划

@SuppressWarnings("all")
public class Code2_猜数字获胜的最小花费_375 {
    public static void main(String[] args) {
        MyUtil.print(guess(3));
    }

    public static int guess(int n) {
        if (n <= 0) {
            return 0;
        }
        return process(1, n);
    }

    /**
     * 数字在L~R范围内获胜的最少花费
     */
    private static int process(int L, int R) {
        // 只有一个数直接选
        if (L == R) {
            return 0;
        }
        // 只有两个数则选较小的，最坏情况肯定会选错，就选花费少的
        if (L == R - 1) {
            return L;
        }
        int min = Integer.MAX_VALUE;
        // 选L
        min = Math.min(min, L + process(L + 1, R));
        // 选R
        min = Math.min(min, R + process(L, R - 1));
        // [L+1, R-1]每个数都有可能
        for (int i = L + 1; i <= R - 1; i++) {
            // 选了i之后，正确的数可能在左边也可能在右边，由于是最差情况，所以要取最大值
            int left = process(L, i - 1);
            int right = process(i + 1, R);
            min = Math.min(min, i + Math.max(left, right));
        }
        return min;
    }


}